#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void BubbleSort(vector<int> &toBeSorted) {
    int size = toBeSorted.size();
    int temp = 0;

    for (int i = 0; i < size - 1; ++i) {            // 总共需要循环比较的次数
        for (int j = 0; j < size - i - 1; ++j) {    // 每次比较中，剩余待比较元素的比较次数
            if (toBeSorted[j] > toBeSorted[j + 1]) {    // 相邻元素两两对比，进行升序排列
                temp = toBeSorted[j];
                toBeSorted[j] = toBeSorted[j+1];
                toBeSorted[j+1] = temp;
            }
        }
    }

    cout << endl;
}

void SelectSort(vector<int>& toBeSorted) {
    int size = toBeSorted.size();
    int minInedx, temp;

    for (size_t i = 0; i < size - 1; i++) {

        minInedx = i;

        for (size_t j = i + 1; j < size; j++) {
            if (toBeSorted[j] < toBeSorted[minInedx])
                minInedx = j;
        }

        temp = toBeSorted[i];
        toBeSorted[i] = toBeSorted[minInedx];
        toBeSorted[minInedx] = temp;
    }

    cout << endl;
}

void InsertionSort(vector<int> &toBeSorted) {
    int size = toBeSorted.size();
    int current, ins_pos;
    for (int i = 1; i < size; i++) {
        current = toBeSorted[i];    // 先拿到待插入元素的值
        ins_pos = i;                // 待插入元素位置

        for (int j = i - 1; (j >= 0) && (toBeSorted[j] > current); --j) {
            toBeSorted[j + 1] = toBeSorted[j]; // 有序序列中的元素x大于待插入元素，x元素后移
            ins_pos = j;                       // 保存该位置，下一个有序序列中的元素小于待插入元素，则不进入循环，利用此位置进行插入
        }

        toBeSorted[ins_pos] = current;         // 遍历得到插入位置后，直接插入待插入的值
    }

    cout << endl;
}

int main() {

    vector<int> myVec;
    myVec.push_back(2);
    myVec.push_back(1);
    myVec.push_back(8);
    myVec.push_back(20);
    myVec.push_back(500);
    myVec.push_back(12);

    for_each(myVec.begin(), myVec.end(),
             [](int val) { cout << val << " "; });

    // BubbleSort(myVec);
    // SelectSort(myVec);
    InsertionSort(myVec);

    for_each(myVec.begin(), myVec.end(),
             [](int val) { cout << val << " "; });

    return EXIT_SUCCESS;
}